{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数 <code>n</code> 和 <code>k</code>，返回 <code>1 ... n</code> 中所有可能的 <code>k</code> 个数的组合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;n = 4, k = 2\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "  [2,4],\n",
    "  [3,4],\n",
    "  [2,3],\n",
    "  [1,2],\n",
    "  [1,3],\n",
    "  [1,4],\n",
    "]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;n = 1, k = 1\n",
    "<strong>输出: </strong>[[1]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 77&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/combinations/\">https://leetcode-cn.com/problems/combinations/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [uUsW3B](https://leetcode.cn/problems/uUsW3B/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [uUsW3B](https://leetcode.cn/problems/uUsW3B/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = [i+1 for i in range(n)]\n",
    "        answer = []\n",
    "        trace = []\n",
    "        def dfs(start:int):\n",
    "            if len(trace) == k:\n",
    "                answer.append(list(trace))\n",
    "            \n",
    "            for i in range(start, n):\n",
    "                trace.append(nums[i])\n",
    "                dfs(i+1)\n",
    "                trace.pop()\n",
    "        dfs(0)\n",
    "        return answer\n",
    "    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        output = []\n",
    "        def addAns(nums, maxNum, need):\n",
    "            if need == 0:\n",
    "                output.append(nums)\n",
    "            else:\n",
    "                for i in range(maxNum + 1, n - need + 2):\n",
    "                    temp = nums[:]\n",
    "                    temp.append(i)\n",
    "                    addAns(temp, i, need - 1)\n",
    "        addAns([], 0, k)\n",
    "        return output \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def helper(bags, nums):\n",
    "            if len(bags) == k:\n",
    "                res.append(bags)\n",
    "                return\n",
    "            elif not nums:\n",
    "                return\n",
    "            bags_1 = bags.copy()\n",
    "            bags_2 = bags.copy()\n",
    "\n",
    "            item = nums.pop()\n",
    "            bags_1.append(item)\n",
    "\n",
    "            helper(bags_1, nums)\n",
    "            helper(bags_2, nums)\n",
    "\n",
    "            nums.append(item)\n",
    "\n",
    "        nums = list(range(1, n + 1))\n",
    "        helper([], nums)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.cur = []\n",
    "\n",
    "    def traceBack(self,n,k):\n",
    "        if len(self.cur) == k:\n",
    "            t = sorted(self.cur)\n",
    "            if t not in self.res:\n",
    "                self.res.append(t)\n",
    "            return\n",
    "        for i in range(1,n+1):\n",
    "            if i not in self.cur:\n",
    "                self.cur.append(i)\n",
    "                self.traceBack(n,k)\n",
    "                self.cur.pop()\n",
    "        \n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if n==k:\n",
    "            return [[i for i in range(1,n+1)]]\n",
    "        if k<=n/2:\n",
    "            self.traceBack(n,k)\n",
    "            return self.res\n",
    "        else:\n",
    "            self.traceBack(n,n-k)\n",
    "            ress = []\n",
    "            for r in self.res:\n",
    "                ress.append(list(set(range(1,n+1))-set(r)))\n",
    "            return ress\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if not 0 < k <= n:\n",
    "            return []\n",
    "        elif k == 1:\n",
    "            return [[i] for i in range(1, n + 1)]\n",
    "        elif k == n:\n",
    "            return [list(range(1, n + 1))]\n",
    "        else:\n",
    "            return self.combine(n - 1, k) + [c + [n] for c in self.combine(n - 1, k - 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        s = [x for x in range(1, n+1)]\n",
    "        ans = list()\n",
    "        def func(k, s, w):\n",
    "            n = len(s)\n",
    "            for i in range(n):\n",
    "                b = w.copy()\n",
    "                b.append(s[i])\n",
    "                if k > 1:\n",
    "                    if i+1 != n:\n",
    "                        func(k-1, s[i+1:], b)\n",
    "                else:\n",
    "                    ans.append(b)\n",
    "        func(k, s, [])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = [i for i in range(1,n+1)]\n",
    "        ans = []\n",
    "\n",
    "        def huisu(cur, tar, ans):\n",
    "            if tar == k:\n",
    "                return [ans]\n",
    "            if cur > n:\n",
    "                return []\n",
    "            tmp = []\n",
    "            tmp.extend(huisu(cur + 1, tar+1, ',' + str(cur) + ans))\n",
    "            tmp.extend(huisu(cur+1, tar,ans))\n",
    "            return tmp\n",
    "        tmp = huisu(1, 0, '')\n",
    "        ans = []\n",
    "        for t in tmp:\n",
    "            t = t.split(',')\n",
    "            ans.append([int(x) for x in t[1::]])\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = set()\n",
    "        res.add(tuple([i for i in range(1, k + 1)]))\n",
    "        # print(res)\n",
    "        for i in range(k + 1, n + 1):\n",
    "            tmp = set()\n",
    "            # print(i)\n",
    "            for r in res:\n",
    "                for j in r:\n",
    "                    tmp.add(tuple([l for l in r if l != j] + [i]))\n",
    "                    # print(r[:j], r[j+1:], [i])\n",
    "            res.update(tmp)\n",
    "\n",
    "        return [list(r) for r in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k == 1:\n",
    "            return [[i] for i in range(1, n + 1)]\n",
    "        if n == k:\n",
    "            return [[i for i in range(1, n + 1)]]\n",
    "        res1 = self.combine(n - 1, k - 1)\n",
    "        res2 = self.combine(n - 1, k)\n",
    "        ans = [x + [n] for x in res1]\n",
    "        return ans + res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k == 0:\n",
    "            return [[]]\n",
    "        if n == k:\n",
    "            return [[i+1 for i in range(n)]]\n",
    "        sub1 = self.combine(n-1, k)\n",
    "        sub2 = self.combine(n-1, k-1)\n",
    "        res = sub1 + [[n]+sub for sub in sub2]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        if k == 1:\n",
    "            for i in range(1, n + 1):\n",
    "                res.append([i])\n",
    "            return res\n",
    "        if k > n:\n",
    "            return []\n",
    "        else:\n",
    "            for i in self.combine(n - 1, k - 1):\n",
    "                res.append(i + [n])\n",
    "            others = self.combine(n - 1, k)\n",
    "            for j in others:\n",
    "                res.append(j)        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def comb(n1,n2,k):\n",
    "            if k==0: return [[]]\n",
    "            res = []\n",
    "            for i in range(n1,n2-k+2):\n",
    "                for r in comb(i+1,n2,k-1):\n",
    "                    res.append(r+[i])\n",
    "            return res\n",
    "        return comb(1,n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def combine(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        def combination(start, end, k):\n",
    "\n",
    "            if k == 1:\n",
    "                return [[k] for k in range(start, end + 1)]\n",
    "\n",
    "            if end - start + 1 == k:\n",
    "                return [[k for k in range(start, end + 1)]]\n",
    "            elif end - start + 1 < k:\n",
    "                return []\n",
    "\n",
    "            return [[start] + k for k in combination(start + 1, end, k - 1)] + combination(start + 1, end, k)\n",
    "\n",
    "\n",
    "        return combination(1, n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def recall(n0,n1,nk):\n",
    "            res = []\n",
    "            if nk == 1:\n",
    "                res = [[i] for i in range(n0,n1+1)]\n",
    "                return res\n",
    "            else:\n",
    "                for i in range(n0,n1):\n",
    "                    temp = recall(i+1,n1,nk-1)\n",
    "                    for j in temp:\n",
    "                        res.append([i]+j)\n",
    "                return res\n",
    "        return recall(1,n,k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(nums,k):\n",
    "            if k == 1:\n",
    "                return [[each_num] for each_num in nums]\n",
    "            elif len(nums) == k:\n",
    "                return [nums]\n",
    "            elif len(nums) < k:\n",
    "                return []\n",
    "            else:\n",
    "                res = []\n",
    "                for i,n in enumerate(nums):\n",
    "                    res += [each_list +[n] for each_list in dfs(nums[i+1:],k-1)]\n",
    "                return res\n",
    "        return dfs(list(range(1,n+1)),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def combine(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        def combination(start, end, k):\n",
    "\n",
    "            if k == 1:\n",
    "                return [[k] for k in range(start, end + 1)]\n",
    "\n",
    "            if end - start + 1 == k:\n",
    "                return [[k for k in range(start, end + 1)]]\n",
    "            elif end - start + 1 < k:\n",
    "                return []\n",
    "\n",
    "            return [[start] + k for k in combination(start + 1, end, k - 1)] + combination(start + 1, end, k)\n",
    "\n",
    "\n",
    "        return combination(1, n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def func(self,nums,k):\n",
    "        if k==0:\n",
    "            return [[]]\n",
    "        n=len(nums)\n",
    "        if n==0:\n",
    "            return [[]] \n",
    "        res=[]\n",
    "        for i in range(n-k+1):\n",
    "            temp=self.func(nums[i+1:],k-1)\n",
    "            temp=[[nums[i]]+r for r in temp]\n",
    "            res.extend(temp)\n",
    "        return res\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k==0:\n",
    "            return [[]]\n",
    "        if n==0:\n",
    "            return [[]]\n",
    "        nums=list(range(1,n+1))\n",
    "        return self.func(nums,k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        subsets = [[]]\n",
    "        result = []\n",
    "        for i in range(1,n+1):\n",
    "            extend_subsets = []\n",
    "            if n-k+1<=i:\n",
    "                min_len = i - (n-k+1)\n",
    "                t = []\n",
    "                if min_len>=0:\n",
    "                    for subset in subsets:\n",
    "                        if min_len <= len(subset):\n",
    "                            t.append(subset)\n",
    "                    subsets = t\n",
    "            for subset in subsets:\n",
    "                extend_subset = [j for j in subset]\n",
    "                extend_subset.append(i)\n",
    "                if len(extend_subset) == k:\n",
    "                    result.append(extend_subset)\n",
    "                else:\n",
    "                    extend_subsets.append(extend_subset)\n",
    "            subsets += extend_subsets\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "\n",
    "        #(n, k) = (n-1, k) + (n-1, k-1)\n",
    "\n",
    "        def dfs(a, c):\n",
    "            if c == 1:\n",
    "                return [[v] for v in a]\n",
    "            \n",
    "            if len(a) < c:\n",
    "                return []\n",
    "            \n",
    "            b = a[1:]\n",
    "            ans = dfs(b, c)\n",
    "\n",
    "            for x in dfs(b, c-1):\n",
    "                ans += [[a[0]] + x]\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return dfs([i for i in range(1, n+1)], k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        def dfs(start,path):\n",
    "            nonlocal res,k\n",
    "            for i in range(start,n+1):\n",
    "                path.append(i)\n",
    "                if len(path) == k:\n",
    "                    res.append(path[:])\n",
    "                dfs(i+1,path)\n",
    "                path.pop()\n",
    "        dfs(1,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def backtrack(n0,n1,nk):\n",
    "            res = []\n",
    "            if nk==1:\n",
    "                res = [[i] for i in range(n0,n1+1)]\n",
    "                return res\n",
    "            else:\n",
    "                for i in range(n0,n1):\n",
    "                    temp = backtrack(i+1,n1,nk-1)\n",
    "                    for j in temp:\n",
    "                        res.append([i]+j)\n",
    "                return res\n",
    "        return backtrack(1,n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def combinefunc(start,n,k):\n",
    "            if k == 1:\n",
    "                return [[i] for i in range(start,n+1)]\n",
    "            else:\n",
    "                res = []\n",
    "                for i in range(start,n-k+2):\n",
    "                    son = combinefunc(i+1,n,k-1)\n",
    "                    res += [[i]+j for j in son]\n",
    "                return res\n",
    "        return combinefunc(1,n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k==1: return([[i] for i in range(1, n+1)])\n",
    "        def a(min_num, p):\n",
    "            if p==1:  return [[i] for i in range(min_num, n+1)]\n",
    "            else:\n",
    "                l = []\n",
    "                for i in range(min_num, n):\n",
    "                    l += [[i] + j for j in a(i+1, p-1)]\n",
    "                return l\n",
    "        return a(1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        a = [i for i in range(1, n+ 1)]\n",
    "        res = []\n",
    "        for it in itertools.combinations(a, k):\n",
    "            res.append(list(it))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        numbers = list(range(1, n+1))\n",
    "\n",
    "        # 使用itertools.combinations生成所有可能的k个数组合\n",
    "        combinations_list = combinations(numbers, k)\n",
    "\n",
    "        # 将每个组合转换为列表形式并返回\n",
    "        return [list(combination) for combination in combinations_list]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.res = []\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtraversal(n, k, 1)\n",
    "        return self.res\n",
    "\n",
    "    def backtraversal(self, n, k, startIdx):\n",
    "        if len(self.path) == k:\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "\n",
    "        for i in range(startIdx, n - (k - len(self.path)) + 2):\n",
    "            self.path.append(i)\n",
    "            self.backtraversal(n, k, i + 1)\n",
    "            self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def backtracking(index,path,result):\n",
    "            if len(path) == k:\n",
    "                result.append(path[:])\n",
    "            for i in range(index,n+1):\n",
    "                path.append(i)\n",
    "                backtracking(i+1,path,result)\n",
    "                path.pop()\n",
    "        result = []\n",
    "        backtracking(1,[],result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def dp(nums: List[int], k: int) -> List[List[int]]:\n",
    "            if k == 1:\n",
    "                return [[num] for num in nums]\n",
    "            n = len(nums)\n",
    "\n",
    "            result = []\n",
    "            for idx in range(n):\n",
    "                select_nums = dp(nums[idx+1:], k-1)\n",
    "                result.extend([[nums[idx]] + tmp for tmp in select_nums])\n",
    "            return result\n",
    "        \n",
    "        return dp(list(range(1, n+1)), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        vis = [1]*n\n",
    "        rres=[]\n",
    "        def dfs(vis,n,k,cur,start):\n",
    "            # res = []\n",
    "\n",
    "            if len(cur)==k:\n",
    "                rres.append(cur)\n",
    "                return\n",
    "                # return [cur]\n",
    "            for tmp in range(start,n+1):\n",
    "                if vis[tmp-1]:\n",
    "                    vis[tmp-1]=0\n",
    "                    dfs(vis,n,k,cur+[tmp],tmp)\n",
    "                    vis[tmp-1]=1\n",
    "            return \n",
    "        dfs(vis,n,k,[],1)\n",
    "        return rres\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(st):\n",
    "            if len(path)==k:\n",
    "                res.append(path.copy())\n",
    "            \n",
    "            #for i in range(st,n+1):\n",
    "            L=len(path)\n",
    "            for i in range(st,n+1):\n",
    "                if len(path)+n+1-st<k:\n",
    "                    break\n",
    "                path.append(i)\n",
    "\n",
    "                dfs(i+1)\n",
    "\n",
    "                path.pop()\n",
    "        \n",
    "        res,path=[],[]\n",
    "        dfs(1)\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "        results = []\n",
    "        nums = list(range(1, n+1))\n",
    "        def dfs(list1, temp):\n",
    "            if len(temp) == k:\n",
    "                results.append(temp.copy())\n",
    "                return\n",
    "            \n",
    "            for i in range(len(list1)):\n",
    "                temp.append(list1[i])\n",
    "                dfs(list1[i+1:], temp)\n",
    "                temp.pop()\n",
    "        \n",
    "        dfs(nums, [])\n",
    "\n",
    "        return results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        results = []\n",
    "        def dfs(start: int, prefix: List[int], remain: int):\n",
    "            if remain == 0:\n",
    "                results.append(prefix)\n",
    "                return\n",
    "            if start > n:\n",
    "                return\n",
    "            dfs(start + 1, prefix, remain)\n",
    "            dfs(start + 1, prefix + [start], remain - 1)\n",
    "        dfs(1, [], k)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if len(path) + n-i+1 < k:\n",
    "                return\n",
    "            if len(path) == k:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i, n+1):\n",
    "                path.append(j)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(combinations(range(1,n+1), k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtrack(1,n,k)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, start,n,k):\n",
    "        if k == len(self.track):\n",
    "            self.res.append(list(self.track))\n",
    "            #return \n",
    "        \n",
    "        for i in range(start,n+1):\n",
    "            self.track.append(i)\n",
    "            self.backtrack(i+1,n,k)\n",
    "            self.track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtracking(n, k, path, res, startindex):\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(startindex, n+1):\n",
    "                path.append(i)\n",
    "                backtracking(n, k, path, res, i+1)\n",
    "                path.pop()\n",
    "        \n",
    "        backtracking(n, k, path, res, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = [ _ for _ in range(1,n+1)]\n",
    "        res = []\n",
    "        \n",
    "        def backtrack(nums, begin, k, path):\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(begin, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtrack(nums, i+1, k, path)\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(nums, 0, k, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        arr, res, path = [], [], []\n",
    "        for i in range(1, n+1):\n",
    "            arr.append(i)\n",
    "\n",
    "\n",
    "        def backTrace(idx, path):\n",
    "            if len(path) + len(arr[idx:]) < k:\n",
    "                return\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                path.append(arr[i])\n",
    "                backTrace(i+1, path)\n",
    "                path.pop()\n",
    "        backTrace(0, path)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Backtrack. Time ((n choose k) * n) Space O(n)\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(combine, idx):\n",
    "            if len(combine) == k:\n",
    "                res.append(combine[:])\n",
    "                return\n",
    "            for i in range(idx, n + 1):\n",
    "                combine.append(i)\n",
    "                dfs(combine, i + 1)\n",
    "                combine.pop()\n",
    "        dfs([], 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def backtrace(i, path):\n",
    "            if len(path) >= k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for j in range(i, n+1):\n",
    "                path.append(j)\n",
    "                backtrace(j+1, path)\n",
    "                path.pop()\n",
    "        backtrace(1, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def dfs(tmp, left):\n",
    "            if len(tmp) == k:\n",
    "                ans.append(tmp)\n",
    "                return \n",
    "            \n",
    "            for i in range(len(left)):\n",
    "                dfs(tmp+[left[i]], left[i+1:])\n",
    "        nums = range(1,n+1)\n",
    "        dfs([],nums)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i: int) -> None:\n",
    "            d = k - len(path)  # 还要选 d 个数\n",
    "            if d == 0:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                path.append(j+1)\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(combinations(range(1,n+1), k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i: int) -> None:\n",
    "            d = k - len(path)  # 还要选 d 个数\n",
    "            if d == 0:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            # 不选 i\n",
    "            if i > d: dfs(i - 1)\n",
    "            # 选 i\n",
    "            path.append(i)\n",
    "            dfs(i - 1)\n",
    "            path.pop()\n",
    "        dfs(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k < 1:\n",
    "            return []\n",
    "        if k > n:\n",
    "            return []\n",
    "        if k == n:\n",
    "            return [list(range(1, n + 1))]\n",
    "        if k == 1:\n",
    "            return [[i] for i in range(1, n + 1)]\n",
    "        # 其余情况\n",
    "        res = []\n",
    "        temp = []\n",
    "        self.backtracking(n, k, 1, res, temp)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def backtracking(self, n, k, startIdx, res, temp):\n",
    "        if len(temp) > k:\n",
    "            return\n",
    "        if len(temp) == k:\n",
    "            res.append(temp[:])\n",
    "            return\n",
    "        for i in range(startIdx, n + 1):\n",
    "            # 入栈\n",
    "            temp.append(i)\n",
    "            # 递归\n",
    "            self.backtracking(n, k, i + 1, res, temp)\n",
    "            # 出栈\n",
    "            temp.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "    \n",
    "    def backtracking(self, start, end, pre, k):\n",
    "        if len(pre) == k:\n",
    "            self.result.append(pre)\n",
    "        else:\n",
    "            new_end = end + 1\n",
    "            for i in range(start, end):\n",
    "                self.backtracking(i + 1, new_end, pre + [i], k)\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtracking(1, n + 2 - k, [], k)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        track = []\n",
    "        def backtrack(start, n):\n",
    "            if len(track) == k:\n",
    "                res.append(track[:])\n",
    "                return\n",
    "            for i in range(start, n+1):\n",
    "                track.append(i)\n",
    "                backtrack(i+1, n)\n",
    "                track.pop(-1)\n",
    "        backtrack(1, n)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        arr, res, path = [], [], []\n",
    "        for i in range(1, n+1):\n",
    "            arr.append(i)\n",
    "\n",
    "\n",
    "        def backTrace(idx, path):\n",
    "            if len(path) + len(arr) < k:\n",
    "                return\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                path.append(arr[i])\n",
    "                backTrace(i+1, path)\n",
    "                path.pop()\n",
    "        backTrace(0, path)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.track = []\n",
    "        self.res = []\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtrack(n,1,k)\n",
    "        return self.res\n",
    "    def backtrack(self,n,start,k):\n",
    "        # base case\n",
    "        if len(self.track)==k:\n",
    "            self.res.append(self.track[:])\n",
    "            return  #不要忘记return \n",
    "\n",
    "        for i in range(start,n+1):\n",
    "            self.track.append(i)\n",
    "\n",
    "            self.backtrack(n,i+1,k)\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return [list(comb) for comb in combinations(range(1, n+1), k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \n",
    "        res = []\n",
    "        def backtrace(start, path):\n",
    "            if len(path) >= k:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(start, n+1):\n",
    "                backtrace(i+1, path+[i])\n",
    "        backtrace(1, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        def dfs(i):    \n",
    "            if len(path)==k:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for a in range(i,n+1):\n",
    "                path.append(a)\n",
    "                dfs(a+1)\n",
    "                path.pop()\n",
    "            return\n",
    "        dfs(1)\n",
    "        return ans    \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \n",
    "        res = []\n",
    "        def backtrace(start, path):\n",
    "            if len(path) >= k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(start, n+1):\n",
    "                backtrace(i+1, path+[i])\n",
    "        backtrace(1, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        def dfs(start, path):\n",
    "            if len(path) == k:\n",
    "                res.append(path)\n",
    "            for i in range(start, n+1):\n",
    "                dfs(i+1, path+[i])\n",
    "        dfs(1, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        if k <= 0 or n < k:\n",
    "            return res \n",
    "        ##\n",
    "        path = []\n",
    "        def backtrack(left, right):\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            if left == right:\n",
    "                return \n",
    "            ##\n",
    "            for i in range(left, right):\n",
    "                path.append(i)\n",
    "                backtrack(i + 1, right)\n",
    "                path.pop()\n",
    "            ##\n",
    "        backtrack(1, n+1)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums = list(range(1,n+1))\n",
    "        def dfs(index,n,path):\n",
    "            if len(path)==k:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for j in range(index,n+1):\n",
    "                path.append(j)\n",
    "                dfs(j+1,n,path)\n",
    "                path.pop()\n",
    "        dfs(1,n,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(i):\n",
    "            # 剪枝，如果当前路径中的值的个数与 [i,n] 中的个数相加都不够 k 个了，直接返回\n",
    "            if len(path) + n-i+1 < k:\n",
    "                return\n",
    "                # 当路径长度等于k的时候加入结果集\n",
    "            if len(path) == k:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "\n",
    "            # 不选当前值\n",
    "            dfs(i+1)\n",
    "\n",
    "            # 选当前值，加入路径\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        # 从1-n个数之间，组合出k位数来（无顺序,那就说明往后去取）\n",
    "        res = []\n",
    "        path = []\n",
    "        def backtracing(n,k,startIndex):  # 确定参数，终止条件和返回值\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "\n",
    "            # 确定单层递归条件\n",
    "            for i in range(startIndex,n+1):\n",
    "                path.append(i)\n",
    "                backtracing(n,k,i+1)\n",
    "                path.pop()\n",
    "        backtracing(n,k,1)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        track = []\n",
    "        def backtrack(start, n):\n",
    "            if len(track) == k:\n",
    "                res.append(track[:])\n",
    "            for i in range(start, n+1):\n",
    "                track.append(i)\n",
    "                backtrack(i+1, n)\n",
    "                track.pop(-1)\n",
    "        backtrack(1, n)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        a = [i for i in range(1,n+1)]\n",
    "        b = list(combinations(a,k))\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/hui-su-sua-56e11/\n",
    "# 元素无重不复选 组合问题\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtrack(n, 1, k)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, n, start, k):\n",
    "        # 终止条件时候要做的事\n",
    "        if len(list(self.track)) == k:\n",
    "            self.res.append(list(self.track))\n",
    "            return\n",
    "        \n",
    "        for i in range(start, n+1): # for 选择 in 选择列表\n",
    "            self.track.append(i) # 做选择\n",
    "            self.backtrack(n, i + 1, k)\n",
    "            self.track.pop()\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        def backtracking(cur, start, count):\n",
    "            if count == k:\n",
    "                nonlocal ans\n",
    "                ans.append(cur.copy())\n",
    "                return\n",
    "            \n",
    "            for i in range(start, n+1):\n",
    "                cur.append(i)\n",
    "                backtracking(cur, i+1, count+1)\n",
    "                cur.pop(-1)\n",
    "\n",
    "        \n",
    "        backtracking([], 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        def dfs(i,k) :\n",
    "            if len(path)==k :\n",
    "                ans.append(path.copy())\n",
    "            last=k-len(path)\n",
    "            if last>n-i+1 :\n",
    "                return\n",
    "            for j in range(i,n+1) :\n",
    "                path.append(j)\n",
    "                dfs(j+1,k)\n",
    "                path.pop()\n",
    "        dfs(1,k)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.n = n\n",
    "        self.ans = []\n",
    "        self.backTrack(k, [], 1)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "\n",
    "    def backTrack(self, k, pre, start):\n",
    "        if len(pre) == k:\n",
    "            self.ans.append(pre.copy())\n",
    "        else:\n",
    "            for j in range(start, self.n + 1):\n",
    "                pre.append(j)\n",
    "                self.backTrack(k, pre, j + 1)\n",
    "                pre.pop()\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/hui-su-sua-56e11/\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        self.backtrack(n, 1, k)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, n, start, k):\n",
    "        # 终止条件时候要做的事\n",
    "        if len(list(self.track)) == k:\n",
    "            self.res.append(list(self.track))\n",
    "            return\n",
    "        \n",
    "        for i in range(start, n+1): # for 选择 in 选择列表\n",
    "            self.track.append(i) # 做选择\n",
    "            self.backtrack(n, i + 1, k)\n",
    "            self.track.pop()\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        tmp = []\n",
    "        ans = []\n",
    "        def dfs(dep):\n",
    "            if len(tmp) == k:\n",
    "                ans.append(tmp[:])\n",
    "                return \n",
    "            i = dep\n",
    "            for j in range(i + 1, n + 1):\n",
    "                tmp.append(j)\n",
    "                dfs(j)\n",
    "                tmp.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i: int) -> None:\n",
    "            d = k - len(path)  # 还要选 d 个数\n",
    "            if d == 0:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i, d - 1, -1):\n",
    "                path.append(j)\n",
    "                dfs(j - 1)\n",
    "                path.pop()\n",
    "        dfs(n)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i: int) -> None:\n",
    "            d = k - len(path)  # 还要选 d 个数\n",
    "            if d == 0:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i, d - 1, -1):\n",
    "                path.append(j)\n",
    "                dfs(j - 1)\n",
    "                path.pop()\n",
    "        dfs(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  \n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        path =[]\n",
    "        ans = []\n",
    "        def backtracking(n, k, start_index):\n",
    "            if len(path) == k:\n",
    "                ans.append(path[:])\n",
    "                return \n",
    "            for i in range(start_index, n+1):\n",
    "                path.append(i)\n",
    "                backtracking(n, k, i+1)\n",
    "                path.pop()\n",
    "\n",
    "        backtracking(n, k, 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = list(range(1, n+1))\n",
    "        res = []\n",
    "        # used = [False] * n\n",
    "        ans = []\n",
    "        def backtrack(start) -> None:\n",
    "            if len(ans) == k: \n",
    "                res.append(list(ans))\n",
    "                return\n",
    "            for i in range(start, n):\n",
    "                ans.append(nums[i])\n",
    "                backtrack(i+1)\n",
    "                ans.pop()\n",
    "        backtrack(0)\n",
    "        return res\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
